2292. Число Фибоначчи

Числа Фибоначчи определяются следующим образом:

F(1) = 1,

F(2) = 1,

F(n) = F (n – 1) + F (n – 2), n ≥ 3

Вычислите n-е число Фибоначчи.

Вход. В первой строке находится количество тестов t (1 ≤ t ≤ 10³). В каждой из следующих t строк содержится одно целое число n (1 ≤ n ≤ 10⁴).

Выход. Для каждого теста выведите соответствующее число Фибоначчи в отдельной строке.

Пример входа	Пример выхода
5 1 2 3 4 5	1 1 2 3 5

РЕШЕНИЕ

числа Фибоначчи

Анализ алгоритма

Поскольку n ≤ 10⁴, для вычисления F(n) необходимо использовать длинную арифметику либо, например, языки программирования Java или Python.

Вычислим числа Фибоначчи от 1 до 10⁴ и сохраним их в массиве fib. Затем для каждого входного значения n выведем элемент fib[n].

Java реализация

import java.util.*;

import java.math.*;

public class Main

{

static BigInteger fib[] = new BigInteger[10001];

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

fib[2] = fib[1] = BigInteger.ONE;

for(int i = 3; i < 10001; i++)

fib[i] = fib[i-1].add(fib[i-2]);

int tests = con.nextInt();

for(int i = 0; i < tests; i++)

{

int n = con.nextInt();

System.out.println(fib[n]);

}

con.close();

}

}

Java реализация – рекурсия с запоминанием

import java.util.*;

import java.math.*;

public class Main

{

static BigInteger fib[] = new BigInteger[10001];

static BigInteger MUNIS1 = new BigInteger("-1");

static BigInteger f(int n)

{

if (n <= 2) return BigInteger.ONE;

if (fib[n].compareTo(MUNIS1) != 0) return fib[n];

return fib[n] = f(n-1).add(f(n - 2));

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

for(int i = 0; i < 10001; i++) fib[i] = MUNIS1;

int tests = con.nextInt();

for(int i = 0; i < tests; i++)

{

int n = con.nextInt();

System.out.println(f(n));

}

con.close();

}

}

Python реализация

Инициализируем первые два числа Фибоначчи: F(1) = 1. F(2) = 1.

f1, f2 = 1, 1

Создаём список fib, в котором будем хранить числа Фибоначчи. Значение F(0) = 0 добавляем специально, чтобы индексация совпадала с условием задачи.

fib = [0, f1, f2]

Вычисляем числа Фибоначчи, вплоть до F(10002).

for i in range(10000):

add = f1 + f2

fib.append(add)

f1, f2 = f2, add

Читаем количество тестов t.

t = int(input())

for i in range(t):

Читаем входное значение n и выводим F(n).

n = int(input())

print(fib[n])